package leetCode.solution;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

/**
 * 最大矩形 给定一个仅包含 0 和 1 、大小为 rows x cols 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
 * 
 * @author jerry
 * @ClassName: Solution85
 * @Description:TODO(描述这个类的作用)
 * @date 2022年11月15日 下午6:09:34
 */
public class Solution84 {

	public static void main(String[] args) {
		int aa[] = new int[] {2,1,5,6,2,3};
		System.out.println(new Solution84().largestRectangleArea(aa));
		System.out.println(new Solution84().largestRectangleArea2(aa));
	}

	// AC不了
	public int largestRectangleArea(int[] heights) {
		int rest = 0;
		
		if(heights==null || heights.length==0) return 0;
		for(int i=0;i<heights.length;i++) {
			int minHeight = heights[i];
			for(int k=i;k>=0;k--) {
				if(heights[k]==0) break;
				minHeight = Math.min(minHeight, heights[k]);
				rest = Math.max(rest, (i-k+1)*minHeight);
			}
		}
		return rest;
    }
	
	public int largestRectangleArea2(int[] heights) {
        int n = heights.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(right, n);
        
        Deque<Integer> mono_stack = new ArrayDeque<Integer>();
        for (int i = 0; i < n; ++i) {
            while (!mono_stack.isEmpty() && heights[mono_stack.peek()] >= heights[i]) {
                right[mono_stack.peek()] = i;
                mono_stack.pop();
            }
            left[i] = (mono_stack.isEmpty() ? -1 : mono_stack.peek());
            mono_stack.push(i);
        }
        
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);
        }
        return ans;
    }

}
